package me.mingshan.leetcode;

/**
 * https://leetcode.cn/problems/linked-list-components/description/
 *
 * 817. 链表组件
 *
 * 给定链表头结点 head，该链表上的每个结点都有一个 唯一的整型值 。同时给定列表 nums，该列表是上述链表中整型值的一个子集。
 *
 * 返回列表 nums 中组件的个数，这里对组件的定义为：链表中一段最长连续结点的值（该值必须在列表 nums 中）构成的集合。
 *
 *
 *
 * 示例 1：
 *
 *
 *
 * 输入: head = [0,1,2,3], nums = [0,1,3]
 * 输出: 2
 * 解释: 链表中,0 和 1 是相连接的，且 nums 中不包含 2，所以 [0, 1] 是 nums 的一个组件，同理 [3] 也是一个组件，故返回 2。
 * 示例 2：
 *
 *
 *
 * 输入: head = [0,1,2,3,4], nums = [0,3,1,4]
 * 输出: 2
 * 解释: 链表中，0 和 1 是相连接的，3 和 4 是相连接的，所以 [0, 1] 和 [3, 4] 是两个组件，故返回 2。
 *
 *
 * @author hanjuntao
 * @date 2025/7/29 0029
 */
public class L_817_linked_list_components {

    public static void main(String[] args) {
        ListNode node1 = new ListNode(0);
        ListNode node2 = new ListNode(1);
        ListNode node3 = new ListNode(2);
        ListNode node4 = new ListNode(3);

        node1.next = node2;
        node2.next = node3;
        node3.next = node4;
        int i = numComponents(node1, new int[]{0, 1,3});
        System.out.println(i);


        ListNode node11 = new ListNode(0);
        ListNode node12 = new ListNode(1);
        ListNode node13 = new ListNode(2);
        ListNode node14 = new ListNode(3);
        ListNode node15 = new ListNode(4);
        node11.next = node12;
        node12.next = node13;
        node13.next = node14;
        node14.next = node15;
        int i1 = numComponents(node11, new int[]{0,3,1,4});
        System.out.println(i1);
    }

    /**
     * 思路：
     *
     * 1. 遍历遍历，统计连续元素的个数（存在nums中）
     * 2. 当遇到不在nums中的元素时，判断前面连续的元素个数是否大于0，大于0则计数
     *
     * @param head
     * @param nums
     * @return
     */
    public static int numComponents(ListNode head, int[] nums) {
        int res = 0;

        ListNode curr = head;

        // 连续元素计数
        int count = 0;

        while (curr != null) {
            // 判断当前元素是否在nums中
            boolean exist = false;
            for (int i = 0; i < nums.length; i++) {
                if (nums[i] == curr.val) {
                    exist = true;
                    break;
                }
            }

            // 存在, 判断前面的元素是否也存在，连续存在
            if (exist) {
                count++;
                // 链表结束
                if (curr.next == null) {
                    res++;
                }
            } else {
                // 不存在
                if (count > 0) {
                    res++;
                }
                count = 0;
            }

            curr = curr.next;
        }

        return res;
    }

}
